1. Field of the Invention
The present invention relates generally to digital computer systems employing caches in their CPUs, and more specifically to digital computer systems employing dual caches the outputs of which can be combined to form desired data.
2. Description of Prior Art--FIGS. 1 and 2
2.1 Introduction to Caches
Many prior art computer systems employ caches in their CPUs. A cache is fast memory within the CPU which is used to store data items frequently used by the CPU in executing programs. Access to data items stored in a cache is more rapid than access to data items contained in the computer system's main memory, and consequently, encachement of frequently-used data items can speed execution of programs by the computer system.
Access to a cache is by means of a key. Data items which may be encached are associated with keys, and the key is input to the cache. If the cache contains the data item associated with the key, the cache outputs the data item; otherwise, the cache produces a cache miss signal. The CPU responds to the cache miss signal by loading the data item corresponding to the key into the cache.
In general, caches are used for two kinds of data items: those which are copies of data items contained in main memory and those which are the results of operations performed by the CPU. FIG. 1 is a block diagram illustrating both uses of caches in prior art computer system. Computer System 101 has two main components: CPU 102 and Main Memory 103. Main Memory 103 contains data items and instructions, and CPU 102 performs operations on the data items in Main Memory 103 in response to instructions. CPU 102 includes two caches, Result Cache 105 and Data Copy Cache 107. Main Memory 103 contains Table 109, containing Table Entries (TEs) 111(1) through 111(n), Table 109', containing TEs 111(1)' through 111(k)', Table Computation Data (TCD) 117, and Encacheable Data 113, containing Encacheable Data Items (EDI) 115(l) through 115(n). TEs 111 are identified by Table Keys (TKs) 110 and EDIs 115 are identified by Data Keys (DKs) 112.
Result Cache 105 contains Result Entries (REs) 106. Each RE 106 contains a VR Field 104 indicating whether RE 106 is valid. A valid RE 106 corresponds to a single TE 111(a) and contains results obtained from computations using TE 111(a) and TCD 117. Valid RE 106 (a) corresponding to TE 111(a) is accessible by means of TK 110 (a) corresponding to TE 111(a).
Data Copy Cache 107 contains Copy Entries (CE) 108. Each CE 108 contains a VC Field 114 indicating whether CE 108 is valid. If it is, CE 106 contains a copy of the data in a single EDI 115(b) and is accessible by means of DK 112(b) corresponding to EDI 115(b).
In both Data Copy Cache 107 and Result Cache 105, a cache miss occurs when a key is presented to the cache and the cache either lacks an entry corresponding to the key or the entry corresponding to the key is invalid. CPU 102 responds to the cache miss by loading the cache entry corresponding to the key. In the case of Data Copy Cache 107, nothing more is involved than fetching the data in the proper EDI 115 from memory and loading it into Data Copy Cache 107 in a CE 108 accessed by the corresponding DK 112. In the case of Result Cache 105, data must be fetched from the proper TE 111 and TCD 117, calculations performed, and the result loaded into the proper RE 106 in Result Cache 105.
2.2 Limitations of Prior-art Caches
The use of caches in any digital computer system is limited by the fact that the encached data items may become invalid. In the caches of FIG. 1, an encached data item may become invalid in one of three ways:
If a data item is a copy of a data item in Main Memory 103, the encached data item becomes invalid when the data item in Main Memory 103 changes its value. PA1 If a key changes its meaning, the encached data item accessed by the key becomes invalid. PA1 If an encached result is calculated using another data item and that data item changes its value, the encached result becomes invalid.
FIG. 1 illustrates all of these possibilities. If EDI 115 (b) changes its value, then CE 108 (b) is no longer a copy of EDI 115 (b) and CE 108 (b) must be invalidated. TK 110 may serve as a key to either Table 109 or Table 109'; if CPU 102 ceases using Table 109 and begins using Table 109', REs 106 do not correspond to TEs 111', and all REs 106 in Result Cache 105 must be invalidated; if a data item in TCD 117 changes its value, all REs 106 in Result Cache 105 depending on that data item must be invalidated. In the last case, it is generally impossible to determine which RE 106 depends on a given data item in TCD 117, so any change generally requires invalidation of all REs 106.
Sometimes, it is possible to reload the invalidated cache entry when it is invalidated. Generally, however, the invalidated cache entry is loaded when a cache miss occurs. Thus, after a change in TCD 117 has invalidated Result Cache 106, Result Cache 106 is gradually reloaded with results calculated from the new value of TCD 117 as misses occur on TKs 110. If TCD 117 does not change value often, the efficiency gained from use of Result Cache 105 outweighs the time required to load it; however, if the changes are frequent, REs 106 are generally invalid and the use of Result Cache 106 in CPU 102 results in no gain or even a loss of efficiency.
2.3 Encachement of Memory Addresses Corresponding to Operands --FIGS. 2 and 2A
The problems of caches just described, together with certain characteristics of standard computer architectures, have made the use of caches difficult in one key area: the translation of an operand which specifies data in an instruction into the memory address of the data. As illustrated in FIG. 2, a typical Instruction 201 for CPU 102 contains an Operation Code 203 and one or more Operands 205. Operation Code 203 specifies an operation to be performed by CPU 102 on data specified by Operand 205. Generally, Operand 205 is a Base-Displacement Operand 207. In such operands, there are at least two fields: RS Field 209, specifying a general-purpose register in CPU 102, and DISP Field 213, containing a binary integer. The integer specifies a displacement, and the specified register in CPU 102 contains a base address. The address of the data represented by Base-Displacement Operand 207 is obtained by adding the displacement specified by DISP Field 213 to the base address contained in the general-purpose register specified by RS Field 207. In addition, Base-Displacement Operand 207 may contain other fields. Here, Base-Displacement Operand 207 further contains an indirection bit, IB 211, specifying that the address in Main Memory 103 obtained by adding the value of DISP Field 213 to the value contained in the register specified by RS Field 207 is not the address of the data represented by the operand, but rather the address of a pointer to the data. A pointer is a data item whose value is the address of data.
FIG. 2A provides an example of how an address is calculated from operands specifying a register containing a base address and a displacement. CPU 102 includes general-purpose register set GPRS 225, containing general-purpose registers R 223(0) through R 223(n). For the purposes of this discussion, a general-purpose register is any register which an instruction executed by CPU 102 may set to an arbitrary value. The contents of a register R 223 is specified in FIG. 2A by cont(x), where x is the number of R 223. Memory 103 contains Memory Portion 215, which in turn contains Data Item 217. Data Item 217 is represented in an instruction by BDO 219, a Base Displacement Operand 205 of the type just described. In BDO 219, b represents the value of RS Field 209 and c the value of DISP 213. R(b) specified by RS Field 209 contains the address in Memor Portion 215 specified by cont(b). Arrow 221 identifies the location specified by cont(b) in Memory Portion 215. CPU 102 obtains the address of Data Item 217 by performing the calculation cont(b) +c.
Base-displacement Operands 207 referring to Data Item 217 may occur over and over in a computer program executing on CPU 102 and Data Item 217's address does not change. Nevertheless, it is impractical to encache Data Item 217's address in a cache employing Base-Displacement Operands 207 as keys. This is the case because such a cache is effectively a result cache like Result Cache 105 of FIG. 1. The contents of each entry in the cache are calculated using the value of R 223 specified in the operand. However, instructions executed by CPU 102 may change the value of that R 223 at any time and in an arbitrary fashion, so the specified R 223 bears the same relationship to the encached address as a data item in TCD 117 bears to a RE 106 calculated from it. Just as the RE 106 must be invalidated each time the data item in TCD 117 it is derived from changes its value, so must the encached address be invalidated each time R 223 specified in the operand corresponding to the address changes its value.
The present invention provides an improved computer system wherein addresses translated from operands may be encached and encachement apparatus wherein certain changes in values used to compute the encached data do not render the encached data invalid. The present invention thereby overcomes the above-mentioned disadvantages of prior art computer systems and encachement apparatus.